package com.learn.finished;

/**
 * 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 *
 * 子数组 是数组中的一个连续部分。
 */
public class num_53 {
    public static void main(String[] args) {
        int[] arr={-2,1,-3,4,-1,2,1,-5,4};//4,-1,2,1
        System.out.println(maxSubArray(arr));//6
    }
    public static int maxSubArray(int[] nums) {
        //如果只有一位，则直接返回
        if (nums.length < 2) {
            return nums[0];
        }
        //sum是记录到当前为止最长的子串和，从nums[0]开始记录
        int sum=nums[0];
        //用于记录目前子串和
        int tmp=0;
        for (int num : nums) {
            //如果目前子串的和大于0，则可以向下一位进行运算，判断是否有能继续增加的条件
            if (tmp > 0) {
                tmp+=num;
            }else {
                //如果当前子串和小于0，则表明其并非最大子串，可以取消对其的记录，从下一位开始重新记录
                tmp=num;
            }
            //从tmp和sum中进行判断，选出最大的子串和，令其成为新的一组最大子串和
            sum=Math.max(tmp,sum);

        }
        //遍历结束，输出最大
        return sum ;
    }
}
